import java.util.Objects;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-04-28
 * Time: 14:29
 */
public class Solution2 {
/*    这是最长公共子序列的进阶版，基础版是只需要求出最长公共子序列的长度，而这个题目是需要得到最长公共子序列，
//    且示例给出的最长公共子序列中只会有一个。
//    对于这个题目，还是有两种做法，
//    一种就是不求最长公共子序列的长度，直接利用动规思想用一个字符串类型的动规数组
//    保存每一个阶段的最长公共子序列，判断方法是和求最长公共子序列的长度是一样的，就是
//            ①：当s1[i-1]==s2[j-1]时
//    dp[i][j]=dp[i-1][j-1]+s1[i-1]
//            ·
//            ②：当s1[i-1]！=s2[j-1]时
//    dp[i][j]=dp[i-1][j].length() > dp[i][j-1].length() ?  dp[i][j-1] : dp[i-1][j];*/
    public String LCS (String s1, String s2) {
        int n=s1.length();
        int m=s2.length();
        //定义一个二维数组存储s1的前i个字符和s2的前j个字符下的最长公共子序列，注意这里不在是长度
        String[][] dp=new String[n+1][m+1];
        //初始化数组，因为这里不在是存储长度，而是存储字符串，所以在没有公共子序列的时候就是“”；
        for(int i = 0;i<=n;i++){
            dp[i][0]="";
        }
        for(int j=0;j<=m;j++){
            dp[0][j]="";
        }
        //构造数组，拼接最长公共子序列，思想和求最长公共子序列的长度是一样的
        for(int i = 1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    //对应字符相等，那么就在前一个最长公共子序列的基础上拼接这个字符
                    dp[i][j]=dp[i-1][j-1]+s1.charAt(i-1);
                }else{
                    //如果不相等，那么就要看s1的前i个字符和s2的前j-1个字符中最长公共子序列的长度
                    // 和s1的前i-1个字符和s2的前j个字符中最长公共子序列的长度谁更长
                    //也就是比较dp[i-1][j]和dp[i][j-1]的长度,谁长就在谁的基础上继续拼接
                    dp[i][j]=dp[i-1][j].length()>dp[i][j-1].length() ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp[n][m].equals("") ? "-1" : dp[n][m];
    }
}
